Query-Time Knowledge Graph Synthesis for Multi-Hop RAG via Asynchronous Agents

Abstract

Graph-based Retrieval-Augmented Generation (GraphRAG) improves multi-hop reasoning but remains limited when required relationships are absent from the knowledge graph despite being supported by textual evidence—a problem we term topological incompleteness. We introduce TSAAT (Topological Synthesis via Asynchronous Agentic Traversal), a query-time framework that synthesizes missing edges during live reasoning. TSAAT deploys asynchronous scout agents that traverse the knowledge graph concurrently and trigger relational hypothesis generation upon frustration. Candidate relations undergo dual-evidence validation: (1) a learned topological plausibility score and (2) textual entailment verification over retrieved corpus evidence. Validated edges are injected into a query-local subgraph, enabling multi-hop reasoning to proceed without offline graph enrichment. On TI-Bench, TSAAT achieves a 91.2% path completion rate (p?

Introduction

This paper addresses limitations in Retrieval-Augmented Generation (RAG) systems, particularly in graph-based approaches like GraphRAG, which improve multi-hop reasoning but are constrained by incomplete knowledge graphs. The key problem identified is topological incompleteness, where valid relationships exist in the text corpus but are missing as edges in the constructed knowledge graph. This differs from knowledge absence or retrieval failure.

To solve this issue, the paper proposes TSAAT (Topological Synthesis via Asynchronous Agentic Traversal), a query-time framework that dynamically discovers and synthesizes missing graph edges. TSAAT introduces:

1. Formal analytical modeling of traversal and synthesis cost.

2. Asynchronous Path Probing (APP) using multiple scout agents that explore the graph in parallel, improving efficiency.

3. Dynamic Contextual Graph Injection (DCGI), a three-phase process (abduction, corpus grounding, and dual-evidence validation) to ensure synthesized edges are both topologically and textually supported.

The system uses frustration detection to trigger synthesis when traversal stalls and employs confidence-based validation to reduce hallucinated edges. Synthesized edges are session-scoped and removed unless highly reliable.

Experiments were conducted on a new benchmark, TI-Bench (Topological Incompleteness Benchmark), which simulates controlled missing edges. Results show that TSAAT significantly outperforms Dense RAG, GraphRAG, and Self-RAG in multi-hop reasoning accuracy. It achieves:

• 88.7% accuracy,

• Major improvements over baselines,

• Faster performance than synchronous multi-agent variants,

• Strong scalability with sublinear latency growth.

Ablation studies confirm that textual grounding and asynchronous execution are critical components. Failure analysis highlights challenges such as entity linking errors and coreference issues.

Conclusion

TSAAT addresses topological incompleteness via query-time graph synthesis. Through asynchronous multi-agent traversal with analytically characterized exploration scaling and dual-evidence validation, it achieves 91.2% path completion—49.1pp over GraphRAG—with 89.5% synthesis precision. The additional token cost may be justified in high-stakes domains where missed relationships have significant consequences.

References

[1] D. Edge, H. Trinh, N. Cheng, J. Bradley, A. Chandra, A. Nguyen, R. Mody, S. Smith, and J. Larson, \"From Local to Global: A Graph RAG Approach to Query-Focused Summarization,\" arXiv:2404.16130, 2024. [2] J. Chen, R. Wang, and M. Liu, \"Multi-Agent Collaborative Knowledge Graph Enrichment via Iterative Refinement,\" arXiv:2312.08091, 2024. [3] P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W. Yih, T. Rocktäschel, S. Riedel, and D. Kiela, \"Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks,\" in Proc. NeurIPS, 2020. [4] S. Borgeaud, A. Mensch, J. Hoffmann, T. Cai, E. Rutherford, K. Millican, G. Van Den Driessche, J. Lespiau, B. Damoc, A. Clark et al., \"Improving Language Models by Retrieving from Trillions of Tokens,\" in Proc. ICML, 2022. [5] V. Karpukhin, B. Oguz, S. Min, P. Lewis, L. Wu, S. Edunov, D. Chen, and W. Yih, \"Dense Passage Retrieval for Open-Domain Question Answering,\" in Proc. EMNLP, 2020. [6] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko, \"Translating Embeddings for Modeling Multi-Relational Data,\" in Proc. NeurIPS, 2013. [7] T. Trouillon, J. Welbl, S. Riedel, E. Gaussier, and G. Bouchard, \"Complex Embeddings for Simple Link Prediction,\" in Proc. ICML, 2016. [8] L. A. Galárraga, C. Teflioudi, K. Hose, and F. Suchanek, \"AMIE: Association Rule Mining under Incomplete Evidence in Ontological Knowledge Bases,\" in Proc. WWW, 2013. [9] V. Parupally, \"CalamanCy: A Tagalog Natural Language Processing Toolkit,\" in Proc. IEEE Int. Conf. on Industrial Technology & Computer Engineering (ICITCE), Penang, Malaysia, 2025, pp. 45–51, doi: 10.1109/ICITCE65255.2025.11210765. [10] J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. Chi, Q. Le, and D. Zhou, \"Chain-of-Thought Prompting Elicits Reasoning in Large Language Models,\" in Proc. NeurIPS, 2022. [11] Z. Jiang, F. F. Xu, L. Gao, Z. Sun, Q. Liu, J. Dwivedi-Yu, Y. Yang, J. Callan, and G. Neubig, \"Active Retrieval Augmented Generation,\" in Proc. EMNLP, 2023. [12] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao, \"ReAct: Synergizing Reasoning and Acting in Language Models,\" in Proc. ICLR, 2023. [13] A. Asai, Z. Wu, Y. Wang, A. Sil, and H. Hajishirzi, \"Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection,\" in Proc. ICLR, 2024. [14] V. R. Parupally, \"A Multi-Objective Game Environment for Evaluating AI Agents,\" in Proc. 2nd Global AI Summit – Int. Conf. on Artificial Intelligence and Emerging Technology (AI Summit), Noida, India, 2025, pp. 692–697, doi: 10.1109/AISummit66170.2025.11410745. [15] V. R. Parupally, \"ATDLLMD: A Test-Driven Framework for Safe, Reliable, and Business-Centric LLM Development,\" IET Conf. Proc., vol. 2025, no. 43, 2025, doi: 10.1049/icp.2025.4778. [16] A. Williams, N. Nangia, and S. Bowman, \"A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference,\" in Proc. NAACL, 2018. [17] S. R. Bowman, G. Angeli, C. Potts, and C. D. Manning, \"A Large Annotated Corpus for Learning Natural Language Inference,\" in Proc. EMNLP, 2015. [18] Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning, \"HotpotQA: A Dataset for Diverse, Explainable Multi-Hop Question Answering,\" in Proc. EMNLP, 2018 [19] X. Ho, A.-K. Duong Nguyen, S. Sugawara, and A. Aizawa, \"Constructing a Multi-Hop QA Dataset for Comprehensive Evaluation of Reasoning Steps,\" in Proc. COLING, 2020. [20] P. Huguet Cabot and R. Navigli, \"REBEL: Relation Extraction By End-to-end Language Generation,\" in Findings of EMNLP, 2021. [21] J. M. van Hulst, F. Hasibi, K. Dercksen, K. Balog, and A. P. de Vries, \"REL: An Entity Linker Standing on the Shoulders of Giants,\" in Proc. SIGIR, 2020. [22] K. Santhanam, O. Khattab, J. Saad-Falcon, C. Potts, and M. Zaharia, \"ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction,\" in Proc. NAACL, 2022.

Copyright

Copyright © 2026 Monisha Gottam. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.